def to_str(n: int, base: int) -> str:
    convert_str = "0123456789ABCDEF"
    if n < base:
        return convert_str[n]
    else:
        return to_str(n // base, base) + to_str(n % base, base)


def sum_list(ls: list):
    if len(ls) == 1:
        return ls[0]
    else:
        return ls[0] + sum_list(ls[1:])


def draw():
    import turtle

    t = turtle.Turtle()
    t.pencolor("red")
    t.pensize(3)
    # 画正方形
    # for m in range(4):
    #     t.forward(100)
    #     t.right(90)

    # 画五角形
    for m in range(5):
        t.forward(400)
        t.right(144)

    t.hideturtle()

    turtle.done()


import turtle


def draw_spiral(t: turtle.Turtle, linelen: int):
    if linelen > 0:
        t.forward(linelen)
        t.right(90)
        draw_spiral(t, linelen - 5)


def draw_tree(t: turtle.Turtle, branch_len: int):
    if branch_len > 5:
        t.forward(branch_len)
        t.right(20)
        draw_tree(t, branch_len - 15)
        t.left(40)
        draw_tree(t, branch_len - 15)
        t.right(20)
        t.backward(branch_len)


# 谢尔宾斯三角形
def draw_trianlge(t: turtle.Turtle, points: dict(), color: str):
    t.fillcolor(color)
    t.penup()
    t.goto(points["top"])

    t.pendown()
    t.begin_fill()
    t.goto(points["left"])
    t.goto(points["right"])
    t.goto(points["top"])

    t.penup()
    t.end_fill()


def get_mid(p1: tuple, p2: tuple) -> tuple:
    return ((p1[0] + p2[0]) / 2, (p1[1] + p2[1]) / 2)


def sierpinski(t: turtle.Turtle, degree: int, points: dict):
    colormap = ["blue", "red", "green", "white", "yellow", "orange"]
    draw_trianlge(t, points, colormap[degree % 6])
    if degree > 0:
        sierpinski(
            t,
            degree - 1,
            {
                "left": points["left"],
                "top": get_mid(points["left"], points["top"]),
                "right": get_mid(points["left"], points["right"]),
            },
        )
        sierpinski(
            t,
            degree - 1,
            {
                "left": get_mid(points["left"], points["top"]),
                "top": points["top"],
                "right": get_mid(points["top"], points["right"]),
            },
        )
        sierpinski(
            t,
            degree - 1,
            {
                "left": get_mid(points["left"], points["right"]),
                "top": get_mid(points["top"], points["right"]),
                "right": points["right"],
            },
        )


def sierpinski_wb(t: turtle.Turtle, degree: int, points: dict, color="white"):
    if degree > 0:
        draw_trianlge(
            t,
            {
                "left": get_mid(points["left"], points["top"]),
                "right": get_mid(points["top"], points["right"]),
                "top": get_mid(points["left"], points["right"]),
            },
            color,
        )

        sierpinski_wb(
            t,
            degree - 1,
            {
                "left": points["left"],
                "top": get_mid(points["left"], points["top"]),
                "right": get_mid(points["left"], points["right"]),
            },
        )
        sierpinski_wb(
            t,
            degree - 1,
            {
                "left": get_mid(points["left"], points["top"]),
                "top": points["top"],
                "right": get_mid(points["top"], points["right"]),
            },
        )
        sierpinski_wb(
            t,
            degree - 1,
            {
                "left": get_mid(points["left"], points["right"]),
                "top": get_mid(points["top"], points["right"]),
                "right": points["right"],
            },
        )


# 汉诺塔题
def move_disk(disk, from_pole, to_pole):
    print(f"Moving disk[{disk}] from {from_pole} to {to_pole}")


def move_tover(height: int, from_pole: str, with_pole: str, to_pole: str):
    if height >= 1:
        move_tover(height - 1, from_pole, to_pole, with_pole)
        move_disk(height, from_pole, to_pole)
        move_tover(height - 1, with_pole, from_pole, to_pole)
